package com.markus.code.newcode;

import java.util.Arrays;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/5 20:21
 * todo: 寻找第k大的数
 */
public class Finder {
    public int findKth(int[] a, int n, int K) {
        // write code here
        if (n < 0 || K > n || K <= 0) {
            return -1;
        }
        return process(a,0,n-1,n,K);
    }

    private int process(int[] a, int L, int R, int n,int K) {
        int value = -1;
        if (L <= R) {
            int[] partition = partition(a, L, R);
            int midL = partition[0];
            int midR = partition[1];
            if (n-K >= midL && n-K <= midR){
                return a[midR];
            }else if (n-K < midL){
                value = process(a,L,partition[0]-1,n,K);
            }else {
                value = process(a,partition[1]+1,R,n,K);
            }
        }
        return value;
    }

    private int[] partition(int[] a, int L, int R) {
        int less = L - 1;
        int more = R;
        while (L < more) {
            if (a[L] < a[R]) {
                swap(a, L++, ++less);
            } else if (a[L] > a[R]) {
                swap(a, L, --more);
            } else {
                L++;
            }
        }
        swap(a, more, R);
        return new int[]{less + 1, more};
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int []arr = {1332802,1177178,1514891,871248,753214,123866,1615405,328656,1540395,968891,1884022,252932,1034406,1455178,821713,486232,860175,1896237,852300,566715,1285209,1845742,883142,259266,520911,1844960,218188,1528217,332380,261485,1111670,16920,1249664,1199799,1959818,1546744,1904944,51047,1176397,190970,48715,349690,673887,1648782,1010556,1165786,937247,986578,798663};
        System.out.println(arr.length);
//        int arr[] = {1,3,5,2,2};
        int n = arr.length;
//        int K = 5;
        int K = 24;
        Finder demo = new Finder();
        System.out.println(demo.findKth(arr,n,K));
        int []a = arr;
        Arrays.sort(a);
        System.out.println(a[25]);
        for (int i : a) {
            System.out.print(i+" ");
        }
    }
}
